/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto& head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            p->next = pMin;
            p = p->next;
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);
        }

        return newnode->next;
    }
};




class Solution {
public:

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        // 定义一个虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = list1, *p2 = list2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};

// 2. 分隔链表
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        // 定义两个虚拟头结点
        // 将原链表分成两条短链表, 一者节点值小于x, 一者节点值不小于x
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;

        ListNode* p = head;

        while(p != nullptr)
        {
            if(p->val < x)
            {
                p1->next = p;
                p1 = p1->next;
            }
            else
            {
                p2->next = p;
                p2 = p2->next;
            }

            p = p->next;
        }

        // 节点值不小于x的短链表尾置空
        p2->next = nullptr;

        p1->next = newnode2->next;
        return newnode1->next;
    }
};




// 3. 合并K个有序链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义一个虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义一个最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        // 将K个链表的头结点插入到最小堆中
        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);

            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
    }
};


// 4. 链表的倒数第K个节点
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        ListNode* p1 = head, *p2 = head;
        ListNode* p = head;

        // p1先走k步, 此时再走n-k步就走到尾了
        for(int i = 0; i < k; i++)
        {
            if(p1) // 防止越界
                p1 = p1->next;
        }

        // p2从头开始和p1一起走, 直至p1指向尾, p2所在的位置就是答案
        while(p1 != nullptr)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 5. 删除链表的倒数第K个节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 定义一个虚拟头结点, 将头结点插入其后 - 防止头删head节点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head;

        // 单链表中删除一个节点需要找到其前一个节点
        // 找单链表中倒数第N个节点
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        ListNode* p1 = head, *p2 = head;
        ListNode* p = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 6. 链表的中间结点
class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};


// 7. 环形链表
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                return true;
        }

        return false;
    }
};



// 8. 环形链表II
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        // slow 从头开始走
        slow = head;

        // slow和fast再次相遇点即为入口点
        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};



// 9. 相交链表
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        ListNode* p1 = headA, *p2 = headB;

        // p1先遍历链表A再遍历链表B, p2先遍历链表B再遍历链表A
        // 保证二者遍历的链表长度相同
        while(p1 != p2)
        {
            if(p1 == nullptr)
                p1 = headB;
            else
                p1 = p1->next;

            if(p2 == nullptr)
                p2 = headA;
            else
                p2 = p2->next;
        }

        return p1;
    }
};



// 剑指offer - 合并排序链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义一个虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        // 将链表数组插入到最小堆中
        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            p->next = pMin;

            if(pMin->next)
                pq.push(pMin->next);

            p = p->next;
        }

        return newnode->next;
    }
};


// 剑指offer - 两个链表的第一个重合交点
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先遍历链表A再遍历链表B, p2先遍历链表B再遍历链表A
        // 这样就保证了遍历链表的长度相同
        ListNode* p1 = headA, *p2 = headB;

        while(p1 != p2)
        {
            if(p1 == nullptr)
                p1 = headB;
            else
                p1 = p1->next;

            if(p2 == nullptr)
                p2 = headA;
            else
                p2 = p2->next;
        }

        return p1;
    }
};



// 剑指offer - 链表中环的入口节点
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head, *fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        // 慢指针从头开始走, 再次和fast指针相遇点即为环的入口节点
        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};


// 剑指offer - 删除链表的倒数第K个节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 为了防止删除头结点, 这里需要定义一个虚拟头结点, 其后链接head节点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head;

        // 单链表中删除一个节点的前提是知道其前一个节点
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        // 定义两个指针
        ListNode* p1 = head, *p2 = head;

        // p1先走K步(此时p1再走n-k步就走尾)
        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        // p2从头开始和p1一起走, 当p1指向空时, p2所在的位置即为答案
        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 剑指offer - 两个链表的第一个公共节点
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先遍历链表A然后遍历链表B, p2先遍历链表B再遍历链表A
        // 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA, *p2 = headB;

        while(p1 != p2)
        {
            if(p1 == nullptr)
                p1 = headB;
            else
                p1 = p1->next;

            if(p2 == nullptr)
                p2 = headA;
            else
                p2 = p2->next;
        }

        return p1;
    }
};



// 剑指offer - 合并两个排序的链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        // 定义一个虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;
        ListNode* p1 = l1, *p2 = l2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};


// 合并K个排序链表 - 较难
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        if(lists.empty())
            return nullptr;

        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            p->next = pMin;

            p = p->next;

            if(pMin->next)
                pq.push(pMin->next);
        }

        return newnode->next;
    }
};



// 分隔链表
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        // 定义两个虚拟头结点
        // 将原链表分成两条短链表, 一者节点值小于x, 一者节点值不小于x
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;

        ListNode* p = head;

        while(p != nullptr)
        {
            if(p->val < x)
            {
                p1->next = p;
                p1 = p1->next;
            }
            else
            {
                p2->next = p;
                p2 = p2->next;
            }

            p = p->next;
        }

        // 节点值不小于x的短链表尾置空
        p2->next = nullptr;

        p1->next = newnode2->next;
        return newnode1->next;
    }
};



// 剑指offer - 合并两个排序的链表
 class Solution {
  453 public:
  454     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
  455     {
  456         // 定义一个虚拟头结点
  457         ListNode* newnode = new ListNode(-1), *p = newnode;
  458         ListNode* p1 = l1, *p2 = l2;
  459 
  460         while(p1 && p2)
  461         {                                                                                                                                              
  462             if(p1->val < p2->val)
  463             {
  464                 p->next = p1;
  465                 p1 = p1->next;
  466             }
  467             else
  468             {
  469                 p->next = p2;
  470                 p2 = p2->next;
  471             }
  472 
  473             p = p->next;
  474         }
  475 
  476         if(p1)
  477             p->next = p1;
  478 
  479         if(p2)
  480             p->next = p2;
  481 
  482         return newnode->next;
  483     }

  };



class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        if(lists.empty())
            return nullptr;

        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            p->next = pMin;

            p = p->next;

            if(pMin->next)
                pq.push(pMin->next);
        }

        return newnode->next;
    }
};


// 
// 链表的倒数第K个节点
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        ListNode* p1 = head, *p2 = head;

        for(int i = 0; i < k ; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 剑指offer - 合并排序链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义一个虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;
        // 定义一个最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }
        
        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);
            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
    }
};



// 剑指offer - 两个链表的第一个交点
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        // 定义两个指针p1和p2, p1先遍历链表A再遍历链表B, p2先遍历链表B再遍历链表A, 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA, *p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }

        return p1;
    }
};



// 剑指offer - 环形链表II
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {

        // 定义快慢指针
        ListNode* slow = head, *fast = head;

        // 判断是否有环
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }

        // 如果是因为循环结束退出则无环
        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};



// 剑指offer - 删除链表的倒数第K个节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 防止删除头结点, 所以定义一个虚拟节点并且指向头结点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head;

        // 单链表中删除一个节点需要先找到该节点
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    // 找到倒数第K个节点
    ListNode* findFromEnd(ListNode* head, int k)
    {
        ListNode* p1 = head, *p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};



// 剑指offer - 两个链表的第一个公共节点
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先遍历链表A再遍历链表B, p2先遍历链表B再遍历链表A, 这样就保证了遍历链表的长度相同
        ListNode* p1 = headA, *p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }    

        return p1;

    }
};


// 剑指offer - 合并两个有序链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        // 定义虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = l1, *p2 = l2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};



// 剑指offer - 链表的倒数第K个节点
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        ListNode* p1 = head, *p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1 != nullptr)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};



// 环形链表
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                return true;
        }

        return false;
    }
};


// 环形链表
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                return true;
        }   

        return false;
    }
};


// 环形链表II
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};

// 相交链表
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先指向链表A再指向链表B， p2先指向链表B再指向链表A， 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }

        return p1;
    }
};

// 删除链表的倒数第K个节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 单链表中删除一个节点需要找到该节点的前一个节点
        // 为了避免删除头节点，这里定义一个虚拟头节点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head;

        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        ListNode* p1 = head;
        ListNode* p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }

};


// 合并两个有序链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        // 定义一个虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;
        ListNode* p1 = list1, *p2 = list2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next =  p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;

    }
};


// 合并K个链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        // 定义一个虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;
        ListNode* p1 = list1, *p2 = list2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next =  p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;

    }
};


// 剑指offer - 合并K个链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);
            
            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
    }
};

/ 分隔链表
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        // 定义两个虚拟头结点
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;
        ListNode* p = head;

        while(p != nullptr)
        {
            if(p->val < x)
            {
                p1->next = p;
                p1 = p1->next;
            }
            else
            {
                p2->next = p;
                p2 = p2->next;
            }
            p = p->next;
        }
        
        p2->next = nullptr;
        p1->next = newnode2->next;

        return newnode1->next;
    }
};



// 合并K个链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);
            
            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
    }
};


// 环形链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);
            
            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
};


class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                return true;
        }    

        return false;
    }
};



// 环形链表II
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }    

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};

// 相交链表
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先指向链表A再指向链表B， p2先指向链表B再指向链表A， 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }    

        return p1;
    }
};


// 删除链表的倒数第N个节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 为避免删除链表的头节点， 我们需要定义一个虚拟头节点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head; // 千万别忘记 - 易忘

        // 单链表中删除一个节点的前提是找到其前一个节点
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        // 定义两个指针p1和p2
        ListNode* p1 = head;
        ListNode* p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1 != nullptr)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 合并两个有序链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        // 定义一个虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = list1, *p2 = list2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }    

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};


// 合并K个升序链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);

            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
    }
};


// 分割链表
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        // 定义两个虚拟头节点
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;
        ListNode* p = head;
        
        while(p != nullptr)
        {
            if(p->val < x)
            {
                p1->next = p;
                p1 = p1->next;
            }
            else
            {
                p2->next = p;
                p2 = p2->next;
            }
            
            p = p->next;
        }

        p2->next = nullptr;
        p1->next = newnode2->next;

        return newnode1->next;

    }
};


// 链表的中间节点
class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};


// 剑指offer - 链表中倒数第K个节点
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        // 定义两个指针p1和p2
        ListNode* p1 = head;
        ListNode* p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1 != nullptr)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;

    }
};


// 剑指offer - 合并两个排序的链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        // 定义虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = l1, *p2 = l2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};


// 剑指offer - 相交链表
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先指向链表A再指向链表B， p2先指向链表B再指向链表A， 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }

        return p1;
    }
};


// 剑指offer - 删除链表的倒数第N个节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 为避免删除头节点， 我们需要定义一个虚拟头节点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head; // 容易忘记这步操作

        // 单链表中删除一个节点的前提是找到其前一个节点
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        ListNode* p1 = head;
        ListNode* p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1 != nullptr)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 剑指offer - 环的入口节点
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;   
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }   

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};


// 剑指offer - 两个链表的第一个重合节点
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针p1和p2, p1先指向链表A再指向链表B， p2先指向链表B再指向链表A， 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else    
                p2 = headA;
        }

        return p1;
    }
};


// 剑指offer - 合并排序链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);

            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
    }
};


// 剑指offer - 合并排序链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义虚拟头节点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b){return a->val > b->val;});

        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            if(pMin->next)
                pq.push(pMin->next);

            p->next = pMin;
            p = p->next;
        }

        return newnode->next;
    }
};

// 相交链表
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针，p1先指向链表A再指向链表B，p2先指向链表B再指向链表A
        // 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else    
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else    
                p2 = headA;
        }    

        return p1;
    }
};


// 剑指offer - 链表中环的入口节点
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head, *fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }    

        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};


// 剑指offer - 删除链表的倒数第n个节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 为避免删除头节点，需要定义一个虚拟头节点，并连接到头节点之前
        ListNode* newnode = new ListNode(-1);
        newnode->next = head;

        // 单链表中删除一个节点需要找到其前一个节点的地址
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        ListNode* p1 = head;
        ListNode* p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 剑指offer - 相交链表
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针,p1先指向链表A再指向链表B，p2先指向链表B再指向链表A
        // 这样就保证了遍历的链表长度相同
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }    

        return p1;
    }
};


// 剑指offer - 合并两个排序的链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        // 定义虚拟节点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = l1, *p2 = l2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};


// 剑指offer - 链表中倒数第k个节点
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        ListNode* p1 = head, *p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 分割链表
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        // 定义两个虚拟节点
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;
        ListNode* p = head;
        
        while(p)
        {
            if(p->val < x)
            {
                p1->next = p;
                p1 = p1->next;
            }
            else
            {
                p2->next = p;
                p2 = p2->next;
            }

            p = p->next;
        }

        p2->next = nullptr;
        p1->next = newnode2->next;

        return newnode1->next;
    }
};


/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:

    // 记录遍历过的节点，防止重复遍历
    unordered_set<Node*> visited;

    // 构建原节点和克隆节点的映射
    unordered_map<Node*, Node*> nodeToIndex;

    Node* cloneGraph(Node* node) 
    {
        // 遍历图节点，并构建克隆图
        traverse(node);

        return nodeToIndex[node];
    }

    void traverse(Node* node)
    {
        if(node == nullptr)
            return;

        if(visited.count(node))
            return;

        // 前序遍历位置
        visited.insert(node);

        if(nodeToIndex.find(node) == nodeToIndex.end())
            nodeToIndex[node] = new Node(node->val);

        // 建立克隆节点
        Node* cloneNode = nodeToIndex[node];

        // 遍历邻居节点，构建克隆图
        for(Node* neighbor : node->neighbors)
        {
            traverse(neighbor);
            // 递归到这，邻居节点一定在哈希表中
            Node* cloneNeighbor = nodeToIndex[neighbor];
            cloneNode->neighbors.push_back(cloneNeighbor);
        }
    }
};


/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:

    // 记录遍历过的节点，防止重复遍历
    unordered_set<Node*> visited;

    // 建立原节点到复制节点的映射；
    unordered_map<Node*, Node*> nodeToClone;

    Node* copyRandomList(Node* head) 
    {
        // 遍历原链表，并复制节点
        traverse(head);

        return nodeToClone[head];
    }

    void traverse(Node* node)
    {
        if(node == nullptr)
            return;

        if(visited.count(node))
            return;

        // 前序遍历位置
        visited.insert(node);

        if(nodeToClone.find(node) == nodeToClone.end())
            nodeToClone[node] = new Node(node->val);

        Node* cloneNode = nodeToClone[node];

        traverse(node->next);
        cloneNode->next = nodeToClone[node->next];

        traverse(node->random);
        cloneNode->random = nodeToClone[node->random];
    }
};


/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:

    // 记录遍历过的节点，防止重复遍历
    unordered_set<Node*> visited;

    // 建立原节点到复制节点的映射；
    unordered_map<Node*, Node*> nodeToClone;

    Node* copyRandomList(Node* head) 
    {
        // 遍历原链表，并复制节点
        traverse(head);

        return nodeToClone[head];
    }

    void traverse(Node* node)
    {
        if(node == nullptr)
            return;

        if(visited.count(node))
            return;

        // 前序遍历位置
        visited.insert(node);

        if(nodeToClone.find(node) == nodeToClone.end())
            nodeToClone[node] = new Node(node->val);

        Node* cloneNode = nodeToClone[node];

        traverse(node->next);
        cloneNode->next = nodeToClone[node->next];

        traverse(node->random);
        cloneNode->random = nodeToClone[node->random];
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        // 定义两个指针p1和p2
        // p1先走k步，p1和p2再同时走
        ListNode* p1 = head, *p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = l1, *p2 = l2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = l1, *p2 = l2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }

        if(p1)
            p->next = p1;

        if(p2)
            p->next = p2;

        return newnode->next;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针，p1指向链表A，p2指向链表B，p1遍历完了链表A就遍历链表B，p2遍历完了链表B就遍历链表A，这样就保证了遍历的链表长度相同
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        while(p1 != p2)
        {
            if(p1)
                p1 = p1->next;
            else
                p1 = headB;

            if(p2)
                p2 = p2->next;
            else
                p2 = headA;
        }    

        return p1;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 定义虚拟头节点并链接在头节点之前，防止删除头节点
        ListNode* newnode = new ListNode(-1);
        newnode->next = head;

        // 单链表中删除一个节点的前提是知道该节点的前一个节点
        ListNode* prev = findFromEnd(newnode, n + 1);

        prev->next = prev->next->next;

        return newnode->next;
    }

    ListNode* findFromEnd(ListNode* head, int k)
    {
        ListNode* p1 = head, *p2 = head;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {   
        // 定义快慢指针
        ListNode* slow = head, *fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }

        // 检查跳出循环
        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        slow = head;

        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq ([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto& head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            ListNode* pMin = pq.top();
            pq.pop();
            p->next = pMin;
            p = p->next;

            if(pMin->next)
                pq.push(pMin->next);
        }

        return newnode->next;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;

        ListNode* p = head;

        while(p != nullptr)
        {
            if(p->val < x)
            {
                p1->next = p;
                p1 = p1->next;
            }
            else
            {
                p2->next = p;
                p2 = p2->next;
            }

            p = p->next;
        }

        p2->next = nullptr;
        p1->next = newnode2->next;

        return newnode1->next;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        // 因为合并两个链表会生成一个新链表，所以定义虚拟指针会简单一些
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = list1, *p2 = list2;

        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }

            p = p->next;
        }    

        if(p2)
            p->next = p2;

        if(p1)
            p->next = p1;

        return newnode->next;
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 排升序 - 定义小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        // 将各个链表的头加入到堆中
        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        // 遍历堆顶元素
        while(!pq.empty())
        {
            ListNode* minNode = pq.top();
            pq.pop();
            p->next = minNode;
            p = p->next;

            if(minNode->next)
            {
                pq.push(minNode->next);
            }
        }

        return newnode->next;
    }
};


